package 剑指Offer._6170;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/27 21:47
 * 圆圈中最后剩下的数字
 * 0,1,···,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。
 * 求出这个圆圈里剩下的最后一个数字。
 * 例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，
 * 则删除的前 4个数字依次是 2、0、4、1，因此最后剩下的数字是 3。
 * 算法：数学
 * 约瑟夫环
 * 每杀掉一个人，就是把数组往前移动了 m 位；然后逆过来，就得到公式
 * 幸存者编号 = f(n, m) = (f(n - 1, m) + m) % n
 * %n 是为了防止越界
 * f(2, 3) = 1; f(3, 3) = 1; f(4, 3) = 0
 * https://blog.csdn.net/u011500062/article/details/72855826
 */
public class _62 {
    public static void main(String[] args) {
        // 2 0 4 1
        System.out.println(lastRemaining(5, 3));
    }

    public static int lastRemaining(int n, int m) {
        int ans = 0;
        for (int i = 2; i <= n; i++) ans = (ans + m) % i;
        return ans;
    }

    public static int lastRemainingList(int n, int m) {
        List<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) list.add(i);
        int idx = 0;
        while (n > 1) {
            idx = (idx + m - 1) % n;
            list.remove(idx);
            --n;
        }
        return list.get(0);
    }

    public static int lastRemainingNum(int n, int m) {
        int[] nums = new int[n];
        Arrays.fill(nums, 1);
        int cnt = 0, cur = 0;
        while (cnt != n - 1) {
            for (int i = 0; i < n; i++) {
                if (nums[i] == 1) {
                    ++cur;
                    if (cur == m) {
                        nums[i] = 0;
                        cur = 0;
                        ++cnt;
                    }
                    if (cnt == n - 1) break;
                }
            }
        }
        for (int i = 0; i < n; i++) if (nums[i] == 1) return i;
        return 0;
    }

}
